package com.algorithm.sort;

/**
 * @program: 插入排序
 * @author: luhd
 * @create: 2021-08-09
 */
public class InsertSorting {
    public static void main(String[] args) {
        /**
         * 对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
         * 从第一个元素开始，该元素可以认为已经被排序；
         */
        int [] arr = {15,5,3,7,9,2,18,10};
        insertionSort(arr);
    }
    public static void insertionSort(int[] arr){
        int len = arr.length;
        for (int i = 1; i < len; i++) {  //因为arr[0]相当于已排序序列，所以从arr[1]开始
            int index = i-1;  //即当前数组下标和前面的数组下标相比较
            int current = arr[i];  //当前未排序序列的第一个值，即待插入数值
            while(index >=0 && arr[index]>current){  //确保数组下标符合条件，其次当未排序序列的第一个值，比前一个值小的时候，应该移位
                arr[index +1] = arr[index];   //将(当未排序序列的第一个值)的前一个值向后移一位
                index --; //当前的数组下标递减，类似于指针向前移位，判断(当未排序序列的第一个值)与前第二位的数值的比较
            }
            arr[index+1] = current;   //最后将待插入数值 插入到合适的位置,前面的index--,所以此处应该+1
        }
        for (int i = 0; i < len; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
